Conventional transforms including the Fast Fourier Transform (FFT), the Fast Hartley Transform (FHT), the Discrete Cosine Transform (DCT), the Discrete Sine Transform (DST), and the Discrete Karhunen-Loeve Transform (KLT) have been used for some time for the compression and decompression of data, where data is separated and combined in the transform domain using radix-2 transforms. The traditional methods that perform separation and combination on the transformed data blocks require that the individual blocks be inversely transformed back to the spatial domain because these existing fast transforms do not have the capability of performing true merge and split strictly in the transform domain. For example, video composing is substantially speedup by performing the operations in the fast transform domain with the transform coefficients having been quantized into integers. The quantization process produces degradation loss of image quality. Manipulation in the transform domain results in further degradation of image quality. To avoid digression when manipulating data in the transform domain, the transformed quantized data is inversely transformed back into the spatial domain, when the data can be further manipulated. However, each time that data is transformed, image quality is degraded. Without true merge and split that would enable convenient repetitive data manipulation in the transform domain, data is disadvantageously transformed back into the time or spatial domain.
A forward transform places a data set from the time domain or spatial domain into the transform domain where the transform domain data can be efficiently transform domain processed. After forward transform domain processing, the transform domain data can be then be inversely transformed back into the original time domain or spatial data with a degradation in data quality when transforming the data due to quantization of the input data set. It is desirable to avoid further data degradation to the data set during transform domain merging, splitting, manipulations, and other transform domain processes.
A forward transform operating on first and second halves of the input data can not simply transform the first and second halves of the input data into a first and a second half transformed output data independently and then simply inversely and independently transform the first and second half back into the original data, due to interdependence across the transformed data set. As such, the transformation process requires some form of combinational processing of both halves of the data set.
To speed transform operations, the prior art has developed fast transforms based on separation and combination transform processing of first and second halves into odd and even transform sets using combinational and transform processing. The transforms are used to place input data into the transform domain for convenient transform domain processing of the transform data. For forward transforms, the input data is in the time domain or spatial domain, and the output data is in the transform domain. Transformation methods use a variety of transforms, the FFT, FHT, DCT, DST, and KLT, in addition to combinational processing that includes twiddle factoring or rotational multiplying, with add and subtract processing. The combinational processing and transform processing define the transform process as either a separating or a combining transformation process.
A separate transform block process transforms first and second input data halves into output transform odd and even halves. The separate transform block process can be a decimation-in-frequency or a decimation-in-time process. The separate transform configuration includes front-end combinational processing followed by N/2 point, that is half-sized, transforms. Input time domain or spatial data is forward transformed into half size transformed data blocks in the transform domain during a separate transformation process where the input data is separated and transformed into transformed even and odd data halves.
A combine transform block process transforms odd and even input data halves into first and second output transforms halves forming a combined transformed output. The combine transform block process can be a decimation-in-time or a decimation-in-frequency transformation process. The combine transform configuration includes front-end N/2 point transforms followed by combinational processing. Input time domain or spatial domain data is forward transformed into combined transformed data in the transform domain during a combine transformation process where the input data halves are combined into combined transformed data. Prior art transform processes are referred to as separate and combine transformation processes, and are not true split and merge transformation processes, because the true merge and split transformation processing enables true splitting and merging in the transform domain, whereas the conventional transforms methods do not.
In editing and composition transform applications, data is often processed in the transform domain. During the initial transformation of an input data set, data is degraded by virtue of quantized truncation to place the output transform data into integers. Such transformed data can then be split and merged without degradation of data quality. However, the prior art transforms require inverse transformations to place the transform domain data back into the time or spatial domain, and then again forward transform time or spatial data, and then combined the transformed data. The inverse transformations and retransformation can result in additional degradation of data quality. The prior art has not developed a systematic generalized approach to true merge and split radix-2 forward transformation. Rather, the prior art teaches a potpourri of disjointed separate and combine radix-2 transform processes that are not true merge and split transforms, but rather separate and combine transformation that disadvantageously require additional inverse transformations and data degradation when separating and combining transform data.
The radix-2 (N/2) transform is a split half transform of a large whole N transform. When radix-2 transforms can be split by two and merged by two without requiring inverse transformations, the processing in the transform domain becomes exceedingly efficient without the loss of data quality when recursively splitting and merging the transformed data. The prior art transforms do not provide true merge and split transform processing because of the required inverse transformations to perfect a combination after a separation, or a separation after a combination of the transformed data. It is highly desirable in data compression applications to have a true merge and split radix-2 transform processing input data halves, where the transformed halves can be directly split and then directly merged in the transform domain without data degradation.
For example, existing fast radix-2 Discrete Cosine Transform algorithms are unable to merge or split data blocks strictly in the DCT domain. In the existing radix-2 algorithms, the DCT matrix must be factorized into two half-sized transform matrices, only one of which is a lower-order DCT preventing the half-sized transforms from being utilized in transform domain processing.
In general, the existing transforms are forward transforms using half-sized transforms followed by or preceded by combinational processing, including scalars, permutations, additions, subtractions, multiplications, and twidders. Data is separated into transform halves using two ½ transforms followed by combinatory logic. Data halves are combined into transform wholes using two ½ transforms followed by combinatory logic. In both forward process transformations, data quality is degraded. The transform halves cannot be merged without firstly inversely transforming transform halves. The transform wholes can not be separated without firstly inversely transforming transform halves. Hence, the existing forward transforms are incapable of successive true merges and splits in any back-and-forth order. Consequently, data is degraded while inversely transforming and data can not be conveniently manipulated in the transform domain without further data degradation. These and other disadvantages are solved or reduced using the invention.